In a data processing apparatus, a cache is typically provided to enable data stored in an external memory, which the processor regularly need to access, to be stored locally to the processor and thus accessed more quickly. Such caches are typically subject to size constraints and therefore the data which is stored therein should be judiciously selected.
Even with careful selection of the data to be stored in the cache, changing requirements of the processor will inevitably mean that occasionally new data will need to be put into the cache, and therefore that an existing entry in the cache will be overwritten. When such overwriting takes place it is typically necessary to check whether the data stored in the cache still corresponds to the original data in the external memory or whether it has changed. If the data stored in the cache has been altered whilst in the cache, and if that data may still be later needed by the processor, then it is typically necessary to take the stored data from the cache and update the corresponding data entry in the external memory. This is commonly known as an “eviction”.
Typically, a data entry in a cache consists not only of the data itself, but is also accompanied by an indication of the memory address of the data (typically in an abbreviated format such as a “TAG”), and attributes indicating, for example, the validity of the data entry in the cache and whether the data entry in the cache has been modified since first being written to the cache. These attributes are commonly referred to as the “valid” bit and the “dirty” bit, respectively. When an allocation request to the cache occurs—a request to overwrite a data entry—the valid and dirty bits of the data entry selected to be overwritten are examined to determine if the data entry needs to be evicted.
In order to determine whether eviction is required without affecting the operation of the processor, it is known to provide an eviction buffer into which the selected cache data entry is transferred, so that the allocation may immediately proceed. Once in the eviction buffer, the valid and dirty bits are examined and if the data entry is “valid AND dirty”, then the data entry is passed to an external bus to be returned to the external memory to update the original entry therein.
Given that there is a time cost to evicting data entries from the cache, in addition to a power cost due to reading out data from the cache, caching policies are typically optimised so that data evictions are relatively rare events. Various algorithms are known which attempt to make best use of a data cache, filling it with the data most useful to the processor and reducing the frequency with which data evictions occur. However, whilst such approaches help to improve the performance of the cache they still can exhibit a number of undesirable characteristics.
It is desired to provide an improved technique for cache eviction.